package com.lmf.Josephu;

/**
 * 约瑟夫问题：实现
 */
public class JosephuDemo {
    public static void main(String[] args) {
        //创建一个单向环形链表
        CircleSingleLinkedList circleList = new CircleSingleLinkedList();
        //添加5个元素
        circleList.autoGenerate(5);
        //打印输出
        circleList.list();
        System.out.println("-------------------");
        //小孩出圈
        circleList.solveJoseph(1,2,5);
    }
}

//创建一个单向环形链表
class CircleSingleLinkedList{
    //创建第一个元素
    Boy first = null;

    //创建添加元素方法,并自动构建成一个环形链表
    public void autoGenerate(int nums){
        //检验nums是否正确
        if (nums < 1) {
            System.out.println("输入编号的值，不正确！");
            return;
        }
        // 辅助指针  帮助构建环形链表
        Boy currentBoy = null;
        //循环创建一个环形单链表
        for (int i = 1; i <= nums ; i++) {
            //根据传入的编号，创建boy对象
            Boy newBoy = new Boy(i);
            //若为第一个添加元素
            if (i == 1) {
                //构建环形链表
                first = newBoy;
                first.setNext(first);
                //辅助指针，指向第一个节点
                currentBoy = newBoy;
//                System.out.println(currentBoy);
            }else {
                //当不为第一个元素的时候,构建环形链表
                currentBoy.setNext(newBoy);
                newBoy.setNext(first);
                //移动辅助指针，为最后一个元素
                currentBoy = newBoy;
//                System.out.println(currentBoy);
            }

        }
    }

    // 遍历当前环形链表
    public void list(){
        //创建一个辅助头指针
        Boy currentBoy = first;
        //判断是否为空
        if (currentBoy.getId() == 0) {
            System.out.println("链表为空，没有数据可以遍历输出！");
            return;
        }
        while (true){
            System.out.println(currentBoy);
            currentBoy = currentBoy.getNext();
            if (currentBoy == first) {
                break;
            }
        }
    }

    /**
     * 根据用户输入，解决约瑟夫问题，计算小孩出圈的顺序问题
     * @param startNo   表示从第几个小孩开始数数
     * @param countNum  表示数几下
     * @param num       表示最初有多少个小孩
     */
    public void solveJoseph(int startNo, int countNum, int num){
        //检验输入的数据格式是否有误
        if ( startNo < 1 || startNo > num || first.getId() < 1) {
            System.out.println("输入的数据有误，请重新输入！");
            return;
        }
        //创建辅助指针变量
        Boy temp = first;
        //让辅助指针指向单向环形链表的最后一项
        while (true){
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
        //随机选取一个人开始报数：小孩报数前，先让first，temp两个指针，后移 startNo-1 下
        while (true){
            for (int i = 0; i < startNo-1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            break;
        }
        while (true){
            //如果只剩下一个节点，就退出循环
            if (temp == first) {
                //打印输出最后一个
                System.out.println(first);
                break;
            }
            //当小孩报数时，同时让first，temp指针后移 countNum-1 下
            for (int i = 0; i < countNum-1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            //打印输出
            System.out.println(first);
            //让最后数到数的小孩出圈,然后首尾再形成单向环形链表
            first = first.getNext();
            temp.setNext(first);
        }
    }
}

//创建链表元素
class Boy{
    private int id;//节点数据：编号
    private Boy next;//保存下一个节点

    public Boy(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "id=" + id +
                '}';
    }
}